package cn.cxq.learning.dynamic_programming;

import org.junit.jupiter.api.Test;

/**
 * 牛客题霸-全部题目
 * 生产口罩
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M 热度指数：1476
 * 本题知识点： 动态规划
 * 算法知识视频讲解
 * 题目描述
 * 牛妹是一家口罩厂家的老板，由于现在疫情严重，牛妹想重新分配每条生产线上的人数来使得能生产的口罩最多。
 * 牛妹所在的公司一共有mm名员工，nn条生产线(0.....n-1)，每条生产线有strategy[i].size种人数安排策略。例如：33个人在aa生产线上，aa生产线每天生产88个口罩；55个人在aa生产线上，每天aa生产线能生产1515个口罩。
 * 牛妹想知道通过合理的策略安排最多每天能生产多少口罩？（可以不用将所有员工都分配上岗，生产线可以选择闲置）
 * <p>
 * 示例1
 * 输入
 * 复制
 * 3,5,[[(1,3),(2,4)],[(3,4),(4,4)],[(8,8)]]
 * 返回值
 * 复制
 * 8
 * 说明
 * 样例解释： 11号生产线采用策略22，22号生产线采用策略11，33号生产线不生产
 * 备注:
 * 1 \leq n,m \leq 2*10^{3} 1≤n,m≤2∗10
 * 3
 * <p>
 * strategy[i].size \ge 1 ,     \sum_{i=0}^{n-1}strategy[i].size \leq 3000strategy[i].size≥1,∑
 * i=0
 * n−1
 * ​
 * strategy[i].size≤3000
 * <p>
 * 1 \leq strategy[i][j].x \leq 2000,1 \leq strategy[i][j].y \leq 30001≤strategy[i][j].x≤2000,1≤strategy[i][j].y≤3000
 * strategy[i][j].x表示人数，strategy[i][j].y表示能生产的口罩数
 */
public class ProduceMask {

    @Test
    public void test() {
        int producemask = producemask(3, 5, new Point[][]{{new Point(1, 3), new Point(2, 4)}, {new Point(3, 4), new Point(4, 4)}, {new Point(8, 8)}});
        System.out.println(producemask);
    }

    // 0/1背包的拓展
    public int producemask(int n, int m, Point[][] strategy) {

        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {

                // 初值即为没有该生产线时的最大值。
                dp[i][j] = dp[i - 1][j];

                // 遍历生产线中的策略，取最优的解
                for (Point p : strategy[i - 1]) {
                    if (p.x <= j) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - p.x] + p.y);
                    }
                }
            }
        }
        return dp[n][m];
    }
}

class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}